 /*******************************************************************************
  * Copyright (c) 2003, 2006 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM - Initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.jobs;

 import java.util.*;

 /**
  * A Queue of objects.
  */
 public class Queue {
     protected Object [] elements;
     protected int head;
     protected boolean reuse;
     protected int tail;

     public Queue() {
         this(20, false);
     }

     /**
      * The parameter reuse indicates what do you want to happen with
      * the object reference when you remove it from the queue. If
      * reuse is false the queue no longer holds a reference to the
      * object when it is removed. If reuse is true you can use the
      * method getNextAvailableObject to get an used object, set its
      * new values and add it again to the queue.
      */
     public Queue(int size, boolean reuse) {
         elements = new Object [size];
         head = tail = 0;
         this.reuse = reuse;
     }

     /**
      * Adds an object to the tail of the queue.
      */
     public void enqueue(Object element) {
         int newTail = increment(tail);
         if (newTail == head) {
             grow();
             newTail = tail + 1;
         }
         elements[tail] = element;
         tail = newTail;
     }

     /**
      * This method does not affect the queue itself. It is only a
      * helper to decrement an index in the queue.
      */
     public int decrement(int index) {
         return (index == 0) ? (elements.length - 1) : index - 1;
     }

     public Iterator elements() {
         /**/
         if (isEmpty())
             return new ArrayList(0).iterator();

         /* if head < tail we can use the same array */
         if (head <= tail)
             return Arrays.asList(elements).iterator();

         /* otherwise we need to create a new array */
         Object [] newElements = new Object [size()];
         int end = (elements.length - head);
         System.arraycopy(elements, head, newElements, 0, end);
         System.arraycopy(elements, 0, newElements, end, tail);
         return Arrays.asList(newElements).iterator();
     }

     public Object get(Object o) {
         int index = head;
         while (index != tail) {
             if (elements[index].equals(o))
                 return elements[index];
             index = increment(index);
         }
         return null;
     }

     /**
      * Removes the given object from the queue. Shifts the underlying array.
      */
     public boolean remove(Object o) {
         int index = head;
         //find the object to remove
 while (index != tail) {
             if (elements[index].equals(o))
                 break;
             index = increment(index);
         }
         //if element wasn't found, return
 if (index == tail)
             return false;
         //store a reference to it (needed for reuse of objects)
 Object toRemove = elements[index];
         int nextIndex = -1;
         while (index != tail) {
             nextIndex = increment(index);
             if (nextIndex != tail)
                 elements[index] = elements[nextIndex];

             index = nextIndex;
         }
         //decrement tail
 tail = decrement(tail);

         //if objects are reused, transfer the reference that is removed to the end of the queue
 //otherwise set the element after the last one to null (to avoid duplicate references)
 elements[tail] = reuse ? toRemove : null;
         return true;
     }

     protected void grow() {
         int newSize = (int) (elements.length * 1.5);
         Object [] newElements = new Object [newSize];
         if (tail >= head)
             System.arraycopy(elements, head, newElements, head, size());
         else {
             int newHead = newSize - (elements.length - head);
             System.arraycopy(elements, 0, newElements, 0, tail + 1);
             System.arraycopy(elements, head, newElements, newHead, (newSize - newHead));
             head = newHead;
         }
         elements = newElements;
     }

     /**
      * This method does not affect the queue itself. It is only a
      * helper to increment an index in the queue.
      */
     public int increment(int index) {
         return (index == (elements.length - 1)) ? 0 : index + 1;
     }

     public boolean isEmpty() {
         return tail == head;
     }

     public Object peek() {
         return elements[head];
     }

     /**
      * Removes an returns the item at the head of the queue.
      */
     public Object dequeue() {
         if (isEmpty())
             return null;
         Object result = peek();
         if (!reuse)
             elements[head] = null;
         head = increment(head);
         return result;
     }

     public int size() {
         return tail > head ? (tail - head) : ((elements.length - head) + tail);
     }

     public String toString() {
         StringBuffer sb = new StringBuffer ();
         sb.append("["); //$NON-NLS-1$
 if (!isEmpty()) {
             Iterator it = elements();
             while (true) {
                 sb.append(it.next());
                 if (it.hasNext())
                     sb.append(", "); //$NON-NLS-1$
 else
                     break;
             }
         }
         sb.append("]"); //$NON-NLS-1$
 return sb.toString();
     }
 }

